<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function Node(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var a = new Node(8)
        var b = new Node(10)
        var c = new Node(4)
        var d = new Node(1)
        var e = new Node(7)
        var f = new Node(15)
        var g = new Node(20)
        var h = new Node(6)
        var i = new Node(5)
        a.left = b
        a.right = c
        b.left = d
        b.right = e
        c.left = f
        c.right = g
        e.left = h
        e.right = i


        /* 
        核心思路：
        1. 要求递归遍历每一个节点，递归这个节点的左右节点是不是要找的目标值 如果是 就返回该节点，需要回溯到父节点，如果要找的左右子节点等于目标值 那么当前的父节点就是 祖先节点
        2. 注意这里即便每次递归 都return了，但是依旧是遍历了每一个节点
           这是怎么做到的呢？
            因为使用了 left和right，后面要进行逻辑判断，才进行返回，而不是立刻返回，因此要遍历了整棵树，
            如果递归后立刻就返回，没有后面的逻辑判断，就不会递归整棵树
        
        */
        var lowestCommonAncestor = function (root, p, q) {
            debugger
            // 1. 递归的退出条件
            // 为了避免root是null 就要把root === null 这个判断条件 写在最前面
            if (root === null || root.val === p || root.val === q) {
                return root
            }
            // 2. 左侧递归 传入左节点，p，q
            let left = lowestCommonAncestor(root.left, p, q)
            // 3. 右侧递归 传入右节点，p，q
            let right = lowestCommonAncestor(root.right, p, q)
            // 4. 单层的逻辑，判断left和right的递归返回值是否是null
            // 如果左右都不是null，说明当前的节点就是祖先节点，返回root
            // 下面if分支里面每一个return 都是为了 每次递归后能够回溯到上一层
            if (left !== null && right !== null) {
                return root
            } else if (left === null && right !== null) {
                // 如果左是null，右不是null，返回右边，
                return right
            } else if (left !== null && right === null) {
                // 如果右边是null，左边不是null，就返回左边
                return left
            } else if (left === null && right === null) {
                // 如果左右都是null，返回null
                return null
            }
        }
        console.log(lowestCommonAncestor(a, 6, 5));
    </script>
</body>

</html>